package com.janushuang.algorithm.sorter;

/**
 * @author zhijing.huang
 *         Created by zhijing.huang on 2014/9/26.
 */
public class HeapSorter<E extends Comparable<E>> extends Sorter<E> {
    @Override
    public void sort(E[] data, int from, int len) {
        buildHeap(data,from,len);

        for (int i = 0; i < len; i++) {
            swap(data,from,from+len-1-i);
            shiftDown(data,from,len-1-i,0);
        }
    }

    private final void shiftDown(E[] data, int from, int len, int pos) {
        E temp = data[from+pos];
        int index = pos*2+1;//left child
        while(index < len) {
            if (index+1<len && data[from+index].compareTo(data[from+index+1])<0) //right child is bigger
            {
                index += 1;
            }
            if (temp.compareTo(data[from+index])<0) {
                data[from+pos] = data[from+index];
                pos = index;
                index = pos*2+1;
            } else {
                break;
            }
        }
        data[from+pos] = temp;
    }

    private final void buildHeap(E[] data, int from, int len) {
        int pos = (len-1)/2;
        for (int i = pos; i >=0 ; i--) {
            shiftDown(data,from,len,i);
        }
    }
}
